package com.leetcode.algorithm.y22.m06;

/**
 * 304. 二维区域和检索 - 矩阵不可变
 * 
 * https://leetcode.cn/problems/range-sum-query-2d-immutable/
 * 
 * @author jie.deng
 *
 */
class NumMatrix {

	private int[][] prefixSumArr = null;

	public NumMatrix(int[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;
		// 前缀和
		// prefixSumArr[i][j] = mat[0...i][0...j]所有元素的和
		prefixSumArr = new int[m][n];
		prefixSumArr[0][0] = matrix[0][0];
		// 第1行前缀和
		for (int j = 1; j < n; j++) {
			prefixSumArr[0][j] = prefixSumArr[0][j - 1] + matrix[0][j];
		}
		// 第1列前缀和
		for (int i = 1; i < m; i++) {
			prefixSumArr[i][0] = prefixSumArr[i - 1][0] + matrix[i][0];
		}
		// 其他行列的前缀和
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				prefixSumArr[i][j] = prefixSumArr[i - 1][j] + prefixSumArr[i][j - 1] - prefixSumArr[i - 1][j - 1]
						+ matrix[i][j];
			}
		}
	}

	public int sumRegion(int row1, int col1, int row2, int col2) {
		int sum = prefixSumArr[row2][col2];
		if (row1 > 0) {
			sum -= prefixSumArr[row1 - 1][col2];
		}
		if (col1 > 0) {
			sum -= prefixSumArr[row2][col1 - 1];
		}
		if (col1 > 0 && row1 > 0) {
			sum += prefixSumArr[row1 - 1][col1 - 1];
		}
		return sum;
	}
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */